/*!
 * \file Hash.h
 *
 * \date Jul 27, 2012
 * \author correa
 *
 * \brief An interface to access the perfect hashing package cmph.
 */

#ifndef HASH_H_
#define HASH_H_

#include <cstdlib>
#include <cmph.h>
#include <assert.h>


/*!
 * \fn hashcompar
 *
 * \brief Standard comparison function for hash operations when the array is small enough
 *
 * \typename T the type of the elements in the hash; it must define the "<" comparison operator
 */
template <typename T>
static int hashcompar(const void *a, const void *b) {
	return *((T *) a) < *((T *) b) ? -1 : *((T *) a) == *((T *) b) ? 0 : 1;
}

/*!
 * \class Hash
 * \brief An interface to packed perfect hashing with cmph.
 *
 * This table uses perfect hashing for constant time access only if the number of elements is
 * greater than 7. Otherwise, binary search in an ordered table is performed.
 *
 * \tparam T the struct of the elements in this parfect hash table
 */
template <typename T>
class Hash {
	friend class Search;

	size_t		key_offset;	//!< in the struct T
	size_t		key_len;	//!< in bytes
	void *		hashtab;	//!< packed table
	size_t		nelem;		//!< number of elements in the table
	size_t		packed_size;//!< size of the packed table

	/*!
	 * \class Search
	 * \brief An interface to the search object.
	 */
	class Search {
		friend class Hash;

		/*!
		 * \brief Computes the index of the specified element in the specified perfect hash table.
		 *
		 * The key's size must be that specified with the constructor.
		 *
		 * \param table perfect hash table
		 * \param key of the element to be searched
		 * \param keylen a key's length, in bytes
		 *
		 */
		virtual size_t search(void * table, const T * key, cmph_uint32 keylen) = 0;
	protected:
		virtual ~Search() {};
	};

	/*!
	 * \class CMPHSearch
	 * \brief An implementation of Search the cmph package
	 */
	class CMPHSearch : public Search {
		friend class Hash;

		size_t search(void * table, const T * key, cmph_uint32 keylen);
	};

	/*!
	 * \class BinSearch
	 * \brief An implementation of Search using binary search in an ordered table.
	 */
	class BinSearch : public Search {
		friend class Hash;

		Hash *	h;	//!< the associated Hash object

		/*!
		 * \brief Creates a new object for the associated Hash object
		 *
		 * \param h the associated Hash object
		 */
		BinSearch(Hash * h) : h(h) {};
		size_t search(void * table, const T * key, cmph_uint32 keylen);
	};

	int (*compar)(const void *, const void *);	//!< it is  expected to have two arguments which point to a key object and to an array member's key, in that order, and should return an integer less than, equal to, or greater than zero if the key object is found, respectively, to be less than, to match, or be greater than the array member.
	Search *		s;		//!< current object Search object
	CMPHSearch * 	cmphs;	//!< Search object to search in the cmph table
	BinSearch * 	bins;	//!< Search object to search in an ordered table

public:
	/*!
	 * \brief Creates an empty parfect hash table.
	 *
	 * \param key_offset to be used in each invocation to \c cmph_io_struct_vector_adapter
	 * \param key_len to be used in each invocation to \c cmph_io_struct_vector_adapter
	 * \param compar comparison function, which is expected to have two arguments which point to a key object and to an array member's key, in that order, and should return an integer less than, equal to, or greater than zero if the key object is found, respectively, to be less than, to match, or be greater than the array member.
	 */
	Hash(size_t key_offset, size_t key_len, int (*compar)(const void *, const void *));
	~Hash();

	/*!
	 * \brief Renews this perfect hash table with the specified keys.
	 *
	 * If this perfect hash table is not empty, then the old table is free'd.
	 *
	 * \param key the table of keys
	 * \param nk number of keys in the specified table
	 */
	void renew(T * key, size_t nk);
	/*!
	 * \brief Computes the index of the specified element in this perfect hash table.
	 *
	 * The key's size must match that specified with the constructor.
	 *
	 * \param key of the element to be searched
	 */
	size_t search(const T *key);
	/*!
	 * \brief Gets the number of elements currently in this parfect hash table.
	 *
	 * \return the number of elements currently in this parfect hash table
	 */
	size_t size();
};

template <typename T>
inline Hash<T>::Hash(size_t key_offset, size_t key_len, int (*compar)(const void *, const void *)) : key_offset(key_offset), key_len(key_len), nelem(0), packed_size(0), compar(compar) {
	cmphs = new Hash<T>::CMPHSearch();
	bins = new Hash<T>::BinSearch(this);
}

template <typename T>
inline Hash<T>::~Hash() {
	if (packed_size > 0) free(hashtab);
	delete cmphs;
	delete bins;
};

template <typename T>
inline void Hash<T>::renew(T * key, size_t nk) {
	if (nk > 7) {
		cmph_io_adapter_t * hash_adapter = cmph_io_struct_vector_adapter(key, sizeof(T), key_offset, key_len, nk);
		cmph_config_t * hash_config = cmph_config_new(hash_adapter);
		cmph_config_set_algo(hash_config, CMPH_CHD);
		//		cmph_config_set_verbosity(hash_config,1);
		cmph_t * h = cmph_new(hash_config);
		nelem = nk;
		s = cmphs;

		int phsz = cmph_packed_size(h);
		if (phsz > packed_size || (phsz << 1) < packed_size) {
			if (packed_size > 0)
				free(hashtab);
			hashtab = malloc(phsz);
			packed_size = phsz;
		}
		cmph_pack(h, hashtab);

		cmph_io_struct_vector_adapter_destroy(hash_adapter);
		cmph_config_destroy(hash_config);
		cmph_destroy(h);
	}
	else {
		nelem = nk;
		s = bins;

		int phsz = nelem * key_len;
		if (phsz > packed_size || (phsz << 1) < packed_size) {
			if (packed_size > 0)
				free(hashtab);
			if (phsz > 0)
				hashtab = malloc(phsz);
			packed_size = phsz;
		}
		memcpy(hashtab, key, phsz);
		qsort(hashtab, nelem, key_len, compar);
	}
}

template <typename T>
inline size_t Hash<T>::search(const T * key) {
	return s->search(hashtab, key, key_len);
}

template <typename T>
inline size_t Hash<T>::size() {
	return nelem;
}

template <typename T>
inline size_t Hash<T>::CMPHSearch::search(void * table, const T * key, cmph_uint32 keylen) {
	return cmph_search_packed(table, (char *) key, keylen);
};

template <typename T>
inline size_t Hash<T>::BinSearch::search(void * table, const T * key, cmph_uint32 keylen) {
	return ((char *) bsearch(key, table, h->nelem, keylen, h->compar) - (char *) table)/keylen;
};
#endif /* HASH_H_ */
